package com.yoho.leet.code.medium;

/**
 * 两个非空的链表，表示两个非负的整数。
 * <br/>
 * 他们的每位都是按逆序的方式存储 如 ： 123  存储为 3->2->1
 * <br/>
 * 将这样的两数相加，并以同样的方式返回
 *
 * @author yhou
 * @ProjectName leetcode
 * @Description:
 * @date 2021/04/21 4:38 下午
 */
public class Subject1 {
    /**
     * 思路：
     * <br/>
     * 1. 链表的数据结构设计
     * <br/>
     * 2. 两个数相加
     * <br/>
     * &nbsp;&nbsp;123
     * <br/>
     * +123
     * <br/>
     * --------
     * <br/>
     * &nbsp;&nbsp;246
     * <br/>
     * 3. 基于存储结构最外的节点是个位,依次个十百千....
     * <br/>
     * 4. 循环外记录上一位节点与满10进位数，由于是按个十百千这样的顺序存储的，所以还要记录个位的节点
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        final ListNode node11 = new ListNode();
        node11.setNumber(5);
        final ListNode node10 = new ListNode();
        node10.setNumber(1);
        node10.setNode(node11);
        // 10 + 10
        System.out.println(node10.toNumber() + "+" + node10.toNumber());
        System.out.println(sum(node10, node10).toNumber());
    }

    public static ListNode sum(ListNode node1, ListNode node2) {
        // 向上进位数
        int i = 0;
        // 前一位的节点
        ListNode node = null;
        // 个位根节点
        ListNode rootNode = null;
        // 个十百千相加
        while (node1 != null || node2 != null || i != 0) {
            ListNode newNode = new ListNode();
            int sum = (node1 != null ? node1.getNumber() : 0) + (node2 != null ? node2.getNumber() : 0) + i;
            i = sum / 10;
            newNode.setNumber(sum % 10);
            if (node != null) {
                //  非个位节点，链接上一位节点
                node.setNode(newNode);
            } else {
                // 将个位节点设置为根节点
                rootNode = newNode;
            }
            node1 = node1 != null ? node1.getNode() : null;
            node2 = node2 != null ? node2.getNode() : null;
            node = newNode;
        }
        return rootNode;
    }

}

/**
 * 节点存储结构
 */
class ListNode {
    private int number = 0;
    private ListNode node;

    public int getNumber() {
        return number;
    }

    public ListNode getNode() {
        return node;
    }

    public void setNode(ListNode node) {
        this.node = node;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    /**
     * 将结构翻译成数字
     * @return
     */
    public String toNumber() {
        return (this.node != null ? this.node.toNumber() : "") + this.number;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("{");
        sb.append("\"number\":")
                .append(number);
        sb.append(",\"node\":")
                .append(node);
        sb.append('}');
        return sb.toString();
    }
}
